import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;


public class StateTree implements java.io.Serializable
{
	private static final long serialVersionUID = 2178257393243565201L;
	private Map<Integer, ArrayList<State>> statesByPosition;
	private int numOfCurrText, amtOfFeatures;
	private State root;
	
	public StateTree(ArrayList<String> texts)
	{
		amtOfFeatures = texts.size();
		numOfCurrText = 0;
		statesByPosition = new HashMap<Integer, ArrayList<State>>();	
		
		boolean[] mask = new boolean[texts.size()];
		for(int i = 0; i < mask.length; i++)
			mask[i] = true;
		
		root = new State(mask, '\u0000');
		createTree(texts);
	}
	
	public State getRoot()
	{
		return root;
	}
	
	public String toString()
	{
		String str = "";
		for(int i = 0; i < statesByPosition.size(); i++)
		{
			str += "Position " + i + ":\n";
			ArrayList<State> states = statesByPosition.get(i);
			for(State s : states)
				str += s + "\n"; 
		}
		
		return str;
	}
	
	
	private void createTree(ArrayList<String> texts)
	{
		for(int i = 0; i < texts.size(); i++)
		{
			addText(texts.get(i));
		}
	}
	
	private boolean containsCharAtThisPos(int pos, char c)
	{
		boolean output = false;
		ArrayList<State> statesInPos = statesByPosition.get(pos);
		
		for(State s : statesInPos)
		{
			if(s.getChar() == c)
				return true;
		}
		
		return output;
	}
	
	private void addText(String text)
	{
		State currNode = root;
		
		for(int pos = 0; pos <= text.length(); pos++)
		{
			char currChar; 
			if(pos == text.length())
				currChar = '\0';
			else
				currChar = text.charAt(pos);
			
			ArrayList<State> statesAtCurrPos = statesByPosition.get(pos);
			
			if(statesAtCurrPos != null && containsCharAtThisPos(pos, currChar))
			{
				State preexistingState = null;
				for(int n = 0; n < statesAtCurrPos.size(); n++)
				{
					preexistingState = statesAtCurrPos.get(n); 
					if(preexistingState.getChar() == currChar)
						break;
				}
				
				boolean[] prevMask = preexistingState.getMask();
				prevMask[numOfCurrText] = true;
				preexistingState.setMask(prevMask);
				currNode.addChild(preexistingState);
				currNode = preexistingState;
			}
			else
			{
				boolean[] newMask = new boolean[amtOfFeatures];
				newMask[numOfCurrText] = true;
				State newChild = new State(newMask, currChar);
				currNode.addChild(newChild);
		
				// If this state is the first state created in this position
				if(statesAtCurrPos == null)
					statesAtCurrPos = new ArrayList<State>();
				
				statesAtCurrPos.add(newChild);
				statesByPosition.put(pos, statesAtCurrPos);
				currNode = currNode.getNextState(currChar);
			}					
		}
		
		numOfCurrText++;
	}
	
	public boolean isMatchListEmpty(boolean[] matchList)
	{
		for(int i = 0; i < matchList.length; i++)
			if(matchList[i])
				return false;
		
		return true;
	}
	
	public boolean isFeaturePresent(String text)
	{
		int maskLength = root.getMask().length;
		
		boolean[] matchList = new boolean[maskLength];
		for(int i = 0; i < maskLength; i++)
			matchList[i] = true;
		
		State currState = root;
		boolean[] currStateMask = new boolean[maskLength];
		text += '\0';
		
		for(int pos = 0; pos < text.length(); pos++)
		{
			State nextState = currState.getNextState(text.charAt(pos));
			if(nextState != null)
			{
				currStateMask = nextState.getMask();
				for(int i = 0; i < maskLength; i++)
					matchList[i] = matchList[i] && currStateMask[i];
				
				currState = nextState;
			}
			else
				return false;
		}
		
		return true;
	}
	
}